package com.example.demo.leetcode.top100;

import java.util.*;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _3最长连续序列
 * @description
 * @date 2023/06/02 22:40
 * <p>
 * ******************************************************
 */
public class _3最长连续序列 {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);

        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] - nums[i - 1] == 0) {
                continue;
            }
            if (nums[i] - nums[i - 1] == 1) {
                list.set(list.size() - 1, list.getLast() + 1);
            } else {
                list.add(1);
            }
        }
        list.sort(Integer::compareTo);
        return list.getLast();
    }


    public int longestConsecutive1(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }

        int ans = 0;
        for (Integer item : set) {
            int curr = item;
            // 如果不存在，代表是一个起点
            if (!set.contains(item - 1)) {
                // 获取到当前节点的连续长度
                while (set.contains(curr + 1)) {
                    curr++;
                }
            }
            // 上个长度和当前长度对比，取大值
            ans = Math.max(ans, curr - item + 1);
        }
        return ans;
    }
}
